﻿using System.Collections.Generic;

namespace DL.Tools.SortAlgorithmTools
{
    public class SortAlgorithm<T>
    {
        /// <summary>
        /// 匹配排序委托  > 大于  < 小于
        /// </summary>
        /// <param name="lhs"></param>
        /// <param name="rhs"></param>
        /// <returns>是否成立</returns>
        public delegate bool Compare(T lhs, T rhs);

        /// <summary>
        /// 插入排序  稳定排序 原地排序  
        /// </summary>
        /// <param name="linkedList">排序数组</param>
        /// <param name="compare"></param>
        public static void InsertSort(LinkedList<T> linkedList, Compare compare)
        {
            if (linkedList == null || linkedList.Count <= 1)
                return;

            LinkedListNode<T> current = linkedList.First.Next; // Start with the second node

            while (current != null)
            {
                T value = current.Value;
                LinkedListNode<T> prev = current.Previous;
                // Find the correct position to insert the current node value
                while (prev != null && compare(value, prev.Value))
                {
                    prev = prev.Previous;
                }
                // If prev is null, it means we need to insert at the beginning
                if (prev == null)
                {
                    linkedList.Remove(current);
                    linkedList.AddFirst(value);
                }
                else
                {
                    linkedList.Remove(current);
                    linkedList.AddAfter(prev, value);
                }
                // Update current to the next node in the original list
                current = current.Next;
            }
        }

    }
}